#include "stack_queue.h"

//构造结点：默认构造函数
listNode::listNode() : data(0), next(nullptr) {}

//构造结点：带参构造函数
listNode::listNode(int nodeData, listNode* succ)
    : data(nodeData), next(succ) {}

//链栈的初始化
MyStack::MyStack()
{
    topNode=NULL;//初始时将栈顶指针置为空
    stackSize=0;//将栈的长度置为0
}

//销毁栈
MyStack::~MyStack()
{
    while(topNode!=NULL)
    {
        listNode *p=topNode;
        topNode=topNode->next;
        delete p;//从栈顶指针开始一个一个销毁
    }
    topNode=NULL;//防止野指针
    stackSize=0;//将链栈长度置为0
}

//入栈
bool MyStack::push(const int& num)
{
    listNode *p=new listNode(num,topNode);//创建一个新的结点，数据域设为要插入的元素num
    if(!p) return false;//创建结点失败
    topNode=p;
    stackSize++;//插入了一个元素，长度增加一个
    return true;
}

//出栈
bool MyStack::pop(int& item)
{
   if(!topNode) return false;
    item = topNode->data;
    listNode* temp = topNode;  
    topNode = topNode->next;   
    delete temp;            
    stackSize--;
    return true;
}

//返回栈顶元素
bool MyStack::getTop(int& item)
{
    if(!topNode) return false;
    item=topNode->data;
    return true;
}

//链栈的打印
void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}

//新增一个循环队列的默认构造函数
MyQueue::MyQueue()
{
    capacity=1000;
    queue=new int[capacity];
    front=rear=0;
}

//循环队列的初始化
MyQueue::MyQueue(const int& cap)
{
    capacity=cap+1;
    queue=new int[capacity];
    front=rear=0;
}
//销毁队列
MyQueue::~MyQueue()
{
    delete[] queue;
}

//清空队列
void MyQueue::clearQueue()
{
    front=rear=0;
}

//入队
bool MyQueue::enQueue(const int& num)
{
    if((rear+1)%capacity==front) return false;//队列已满，无法入队
    queue[rear]=num;//入队
    rear=(rear+1)%capacity;//尾指针增1
    return true;
}

//出队
bool MyQueue::deQueue(int& item)
{
    if(front==rear) return false;//队空，无法出队
    item=queue[front];
    front=(front+1)%capacity;
    return true;
}

//返回队头元素
bool MyQueue::getFront(int& item)
{
    if(front==rear) return false;//队空，无法出队
    item=queue[front];
    return true;
}

int MyQueue::size() 
{
    return (rear - front + capacity) % capacity;
}
   
bool MyQueue::getAt(int idx, int& out) 
{
    if (idx < 0 || idx >= size()) return false;
    out = queue[(front + idx) % capacity];
    return true;
}

//循环队列的打印
void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

//判断栈是否为空的函数
bool MyStack::Empty()
{
    if(topNode==NULL) return 1;
    return 0; 
}

//不将栈顶元素进行存放的出栈函数
bool MyStack::pop1()
{
     if(!topNode) return false;
    listNode* temp = topNode;  
    topNode = topNode->next;   
    delete temp;               
    stackSize--;
    return true;
}

//返回栈顶元素(返回值为int)
int MyStack::Top()
{
    if(!topNode) return -1;
    int item=topNode->data;
    return item;
}

//判断优先级的函数
int prec(char op)
{
    if(op=='+'||op=='-') return 1;
    if(op=='*'||op=='/') return 2;
    return 0;

}

//中缀表达式转后缀表达式
bool postfixExpression(const string& str, string& result)
{
    int tmp;
    MyStack st;
    for(int i=0;i<str.length();i++)
    {
        if(str[i]>='0'&&str[i]<='9') 
        {
             result+=str[i];
        }
        else if(str[i]=='(') st.push(str[i]);
        else if(str[i]==')') 
        {
            while(!st.Empty()&&st.Top()!='(')
            {
                result+=st.Top();
                st.pop1();
            }
            if (st.Empty() || st.Top() != '(') {
                result = "Expression is wrong!";
                return false;
            }
            st.pop1();
        }
        else if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/')
        {
            while(!st.Empty()&&st.Top()!='('&&prec(st.Top())>=prec(str[i]))
            {
                result+=(st.Top());
                st.pop1();
            }
            st.push(str[i]);
        }
        else 
        {
            result="Expression is wrong!";
            return false;
        }
    }
    while (!st.Empty())
    {
    if (st.Top() == '(')
    {
        result = "Expression is wrong!";
        return false;
    }
    result += st.Top();
    st.pop1();
    }
    return true;
}

//表达式求值
bool expressionVal(const string& str, int& result)
{
    string s;
    int a,b,c;
    if(!postfixExpression(str,s)) return false;
    MyStack st;
    for(int i=0;i<s.length();i++)
    {
        char d=s[i];
        if (d>='0'&&d<='9') 
        {
            st.push(d-'0');
        }
        else if (d=='+'||d=='-'||d=='*'||d=='/')
        {
           if (!st.getTop(a)) return false;  // 真正的空栈错误
           st.pop1();
           if (!st.getTop(b)) return false;
           st.pop1();
            switch (d)
            {
            case '+':
                c=b+a;
                break;
            case '-':
                c=b-a;
                break;
            case '*':
                c=b*a;
                break;
            case '/':
                if (a == 0) return false;
                c=b/a;
                break;
            default:
                break;
            }
            st.push(c);
        }
        else return false;
    }
    int ans;
    if (!st.getTop(ans)) return false;  
    if (!st.Empty()) return false;
    result = ans;
    return true;
}

//杨辉三角
void yanghui(const int& n)
{
    MyQueue q1(1000), q2(1000);      
    q1.enQueue(1); 

    for (int i = 2; i <= n + 1; ++i) {   
        MyQueue &cur = (i & 1) ? q2 : q1;  
        MyQueue &prev = (i & 1) ? q1 : q2; 
        cur.clearQueue();        

        cur.enQueue(1);
        for (int j = 0; j < i - 2; ++j) {
            int left, right;
            prev.getAt(j, left);
            prev.getAt(j + 1, right);
            cur.enQueue(left + right);
        }
        cur.enQueue(1);
        cur.printQueue();  
    }
}